gravicom

A web-based tool for community detection in networks

• Introduction/Background
• User Interface
• Demo
• Graphical Devices
• Technical Aspects
• Further Work

Who cares and why did we make this?

• Many relationships easily conceptualized as a graph/network
• A graph is defined as a collection of nodes (entities) and edges (relationships)
• Examples of such relationships include:
  • social networks (sociology)
  • the world wide web (computer science)
  • protein networks (biology)

• A community is defined as a group of nodes in a graph that share properties
• Community structure - collection of nodes which are densely linked to nodes within the community and sparsely linked to notes outside
• Current methodology for community detection often involves an algorithmic approach; partitions a graph into node clusters iteratively before stopping criterion
• First define an objective function and then optimize

• Example objective function: Girvan & Newman’s modularity measure
  

\[ Q = \sum\limits_r (e_{rr} - a_r^2) \] \( r = \) a community
\( e_{rr} = \) fraction of links that connect two nodes inside the community
\( a_r = \) the fraction of links that have one or both vertices inside the community

• Interpretation: fraction of edges that connect vertices of the same type minus the expected value of the same quantity in a network with the same community divisions but random edges
  

\( Q = 0 \): number of within-community edges no better than random
\( Q \in [0.3, 0.7] \): strong community structure
\( Q=1 \): maximum value

• Modularity is not the only useful objective function
• Simple proportion: quantification of density within the community vs. sparcity outside

\[ \pi(S) = \frac{\#\text{ of edges within } S}{\#\text{ of edges leaving} S} \]

• Similar idea: Conductance

\[ \phi(S) = \frac{\#\text{ of edges leaving} S}{\sum\limits_{u \in S} \text{degree of } u} \] (double counting of edges within community \( S \))

• Search for an optimal modularity value is NP-hard
• The number of possible partitions of the network requires \( 2^n \) complexity
• In fact, the optimization of an objective function is typically an NP-hard problem

• Heuristics used to optimize the objective function in a reasonable amount of time
• Heuristic-based clustering is useful because this offers an automated way to perform community detection

The main elements of the problem themselves [graph clustering], i.e. the concepts of community and partition, are not rigorously defined, and require some degree of arbitrariness and/or common sense. (Fortunato, 2010)

• Heuristics are not the solution.

• Communities are often fuzzily-defined human concepts
• Address this by adding element of human judgement
• Introduce a novel visualization-based community detection tool, gravicom

• Allows users to
  • Visually direct and interact with the steps of community detection
  • Assess the created clusters through visual and quantitative summaries
• Standalone exploratory tool for graph data
• Initial state to be passed to a community detection algorithm in order reduce the complexity of optimization

Meet gravicom

(1) Control Panel, (2) Data Management, (3) Connection Table, (4) Graph Display, and (5) Tabset

http://shiny1.iastate.edu/andeek/gravicom
(must be VPNed to internal ISU network)

• Through manual specification of conferences, we were able to correctly classify 91.3 % of the football teams into their conferences.

• Political books co-purchased close to the 2004 United States presidential election and sold on Amazon.com

• Correctly classified 86.67 % of the books into the categories created by the author of the data set.

Theory behind the curtain

• Graph layout is an assignment of a Cartesian coordinate to each node for display in 2D or 3D
• Layout of a graph significantly affects the number of communities that users detect within a graph
• Humans used to detect communities \( \Rightarrow \) special attention needs to be paid to the layout being used
• Location of a node spatially relative to other nodes in a cluster has a significant effect on user: “adjacent nodes must be placed near to each other if possible” (McGrath, Blythe, and Krackhardt, 1996)

• Physics based algorithm for graph drawing
• Repulsive forces (charged particles) used to separate all pairs of nodes
• Links are fixed-distance geometric constraints
• Groups of nodes sharing multiple edges are pulled in closer proximity
• Pseudo-gravity force keeps nodes centered in the visible area and avoids expulsion of disconnected subgraphs

• Difficult to glean meaning from a visual representation in large/complex graphs
• Replace repeated patterns in a graph by a representation, to simplify a network
• Fewer nodes and edges to display \( \Rightarrow \) visual complexity of the graph visualization is greatly reduced
• Allows the user to analyze the network structure more accurately

What makes it tick?

GML file structure:

graph
[
  directed 0
  node
  [
    id 0
    label "Node 1"
    value 100
  ]
  node
  [
    id 1
    label "Node 2"
    value 200
  ]
  edge
  [
    source 1
    target 0
  ]
]

JSON file structure:

{
  "nodes":
  [{"id":"n0","v_id":"0","v_label":"Node 1","v_value":"100"}, 
   {"id":"n1","v_id":"1","v_label":"Node 2","v_value":"200"}], 
 "edges":
  [{"source":0, "target":1}]
}

Possible extensions to gravicom

• Combine the benefits of human detection of communities with algorithmic detection
• Visual detection of communities serves as an initialization step
• Pass to iterative algorithm
• User tracks progress and has power to dynamically set stopping criterion

• View a dynamic graph across time – how the edges change between nodes
• Detect time-dependent communities
• Add optional node labels to track progress

Thank you!